public class 小行星碰撞 {
    public int[] asteroidCollision(int[] asteroids) {
        int n = asteroids.length;
        int[] stack = new int[n]; // 数组模拟栈
        int cnt = 0; // 长度
        for (int i = 0;i < n;i++) {
            stack[cnt++] = asteroids[i]; // 先入栈
            // 栈中要大于 1 个元素才可以发生碰撞
            while (cnt > 1) {
                int cur = stack[cnt - 1]; // 当前的元素
                int pre = stack[cnt - 2]; // 前一个元素
                // 会碰撞的条件
                if (cur < 0 && pre > 0) {
                    // 相同直接两个都没掉
                    if (-cur == pre) {
                        cnt -= 2;
                    } else if (-cur > pre) {
                        // 后一个大, 需要碰撞掉前一个
                        cnt -= 2;
                        stack[cnt++] = cur;
                    } else {
                        // 前一个更大
                        cnt--;
                    }
                } else {
                    // 其他情况不会碰撞
                    break;
                }
            }
        }
        // 重填数组
        int[] ans = new int[cnt];
        for (int i = 0;i < cnt;i++) {
            ans[i] = stack[i];
        }
        return ans;
    }
}
